package com.wxweven.algorithm.list;

/**
 * @author wxweven
 */
public class LC234判断是否为回文链表 {

    /*
     * 输入: 1->2->null
     * 输出: false
     *
     * 输入: 1->2->2->1->null
     * 输出: true
     */

    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return true;
        }

        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        ListNode midNext = slow;
        if (fast != null) {
            midNext = slow.next;
        }

        ListNode tail = reverse(midNext);

        while (tail != null) {
            if (tail.val != head.val) {
                return false;
            }
            tail = tail.next;
            head = head.next;
        }

        return true;
    }

    public ListNode reverse(ListNode head) {
        if (head == null) {
            return null;
        }

        ListNode prev = null;
        ListNode next = null;
        while (head != null) {
            next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }

        return prev;
    }
}